# class ElemType:
#     def __init__(self, key, otherinfo=None):
#         self.key = key  # 关键字域
#         self.otherinfo = otherinfo  # 其他域
#
#
# def shell_insert(r, dk):
#     # 对顺序表r做一趟增量是dk的希尔插入排序
#     for i in range(dk + 1, len(r)):
#         if r[i].key < r[i - dk].key:  # 需将r[i]插入有序增量子表
#             r[0] = r[i]  # 暂存在L.r[0]，补全此处
#             j = i - dk
#             while j > 0 and r[0].key < r[j].key:
#                 r[j + dk] = r[j]  # 记录后移，直到找到插入位置，补全此处
#                 j -= dk
#             r[j + dk] = r[0]  # 将r[0]即原r[i]，插入到正确位置
#     return r
#
#
# def shell_sort(r, dt):
#     # 按增量序列dt[0..t-1]对顺序表r作t趟希尔排序
#     for dk in dt:
#         r = shell_insert(r, dk)  # 一趟增量为dt[t]的希尔插入排序
#     return r
#
#
# if __name__ == '__main__':
#     input_string = input('请输入要排序的整数序列，用空格隔开:')
#     nums = input_string.split(' ')  # 分隔输入串
#     r = [ElemType(key=None)] + [ElemType(int(i)) for i in nums]  # 下标0添加一个空位
#     dt = [5, 3, 1]  # dt数组
#     print('希尔排序的结果为:', [_.key for _ in shell_sort(r, dt)[1:]])  # 不输出用于辅助的第一位




class ElemType:
    def __init__(self, key, otherinfo=None):
        self.key = key  # 关键字域
        self.otherinfo = otherinfo  # 其他域


def merge(r, t, low, mid, high):
    # 将有序表r[low..mid]和r[mid+1..high]归并为有序表t[low..high]
    i = low
j = mid + 1
    k = low
    while i <= mid and j <= high:  # 将r中记录由小到大地并入t中
        if r[i].key <= r[j].key:
            t[k] = r[i]
            k += 1
            i += 1
        else:
            t[k] = r[j]
            k += 1
            j += 1
    while i <= mid:
        t[k] = r[i]  # 将剩余的r[i..mid]复制到t中
        k += 1
        i += 1
    while j <= high:
        t[k] = r[j]  # 将剩余的r[j..high]复制到t中
        k += 1
        j += 1
    return t


def m_sort(r, t, low, high):
    # r[low..high]归并排序后放入t[low..high]中
    if low == high:
        t[low] = r[low]
    else:
        mid = int((low + high) / 2)  # 将当前序列一分为二，求出分裂点mid
        s = [0 for _ in range(len(r))]  # 初始化s
        s = m_sort(r, s, low, mid)  # 对子序列r[low..mid]递归归并排序，结果放入s[low..mid]
        s = m_sort(r, s, mid + 1, high)  # 对子序列r[mid+1..high]递归归并排序，结果放入s[mid+1..high]
        t = merge(s, t, low, mid, high)  # 将s[low..mid]和s[mid+1..high]归并到t[low..high]
    return t


def merge_sort(r):
    # 对顺序表r做归并排序
    return m_sort(r, r, 1, len(r) - 1)


if __name__ == '__main__':
    input_string = input('请输入要排序的整数序列，用空格隔开:')
    nums = input_string.split(' ')  # 分隔输入串
    r = [ElemType(key=None)] + [ElemType(int(i)) for i in nums]  # 下标0添加一个空位
    print('归并排序的结果为:', [_.key for _ in merge_sort(r)[1:]])  # 不输出用于辅助的第一位